package sudoku;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;

/** Class represents classic Sudoku game board which holds all cell objects.
 *
 * @author Taras Basiuk
 * @version 0.1 * 
 */
public class ClassicGrid implements Cloneable{


    /** 
     * This map contains references to cell objects with key values
     * correspond to rowPosition value of cell. 
     */
    private Map<Integer, ClassicCell> rows;

    /** 
     * This map contains references to cell objects with key values
     * correspond to columnPosition value of cell. 
     */
    private Map<Integer, ClassicCell> columns;

    /** 
     * This map contains references to cell object with key values
     * correspond to squarePosition value of cell. 
     */
    private Map<Integer, ClassicCell> squares;

    /** 
     *  Array list contains references to cell objects, usually sorted.
     *  Used to pick cell with least available possible values. 
     */
    private ArrayList<ClassicCell> possibleValues;
    
    /** Value of number of total cells on the board. */
    private int numCells;

    /** Value of number of unsolved cells on the board. */
    private int unsolvedCells;
    
    /** Value indicates level of square sudoku board. For default board, level=3.*/
    private int level;
    
    /** Value indicates number of cells with no duplicate values. */
    private int neighbors;

    /** Default constructor. Creates 81 cell and fills corresponding maps and
     list with references to these cells. Sets number of unsolved cells to 81.*/
    public ClassicGrid(){

        this(3);

    }
    
    /** Constructor which creates a square sudoku game grid of a given level.*/
    public ClassicGrid(int lev){

        rows = new TreeMap();
        columns = new TreeMap();
        squares = new TreeMap();
 
        possibleValues = new ArrayList();
        
        if (lev>2 && lev<6) level = lev;
        else level = 3;
        
        neighbors = level * level;        
        numCells = level * level * level * level;        
        unsolvedCells = numCells; 
        
        for(int i = 0; i<numCells; i++){

            int rowN = i;
            int colN = colN_from_rowN(rowN);
            int sqrN = sqrN_from_rowN(rowN);

            ClassicCell c = new ClassicCell(rowN, colN, sqrN, neighbors);

            rows.put(rowN, c);
            columns.put(colN, c);
            squares.put(sqrN, c);

            possibleValues.add(c);
        }
    }
    
    /** 
     * Constructor which creates a copy of another DataGrid by taking data from
     * copied ClassicGrid.rows map of that ClassicGrid. Gets called by DataGrid.clone() method.
     * copy map assumed to be valid.
     * @param copy Copied ClassicGrid.rows map from which data for this ClassicGrid will be taken. 
     */
    public ClassicGrid(TreeMap<Integer, ClassicCell> copy){
        
        rows = copy;
        columns = new TreeMap();
        squares = new TreeMap();
 
        possibleValues = new ArrayList();
        
        level = (int) Math.pow(copy.size(), 0.25);
        
        neighbors = level * level;        
        numCells = level * level * level * level;        
        unsolvedCells = numCells;         

        for(int i = 0; i<numCells; i++){

            int rowN = i;
            int colN = colN_from_rowN(rowN);
            int sqrN = sqrN_from_rowN(rowN);

            ClassicCell c = rows.get(i);

            columns.put(colN, c);
            squares.put(sqrN, c);

            possibleValues.add(c);
            
            if (c.getValue() != 0) unsolvedCells--;
        }
    }

    /** Private method returns cell column number from given row cell number.*/
    private int colN_from_rowN(int rN){
        return (rN%neighbors)*neighbors + (rN/neighbors);
    }

    /** Private method returns cell square number from given row cell number.*/
    private int sqrN_from_rowN(int rN){
        return (rN/(neighbors*level))*(neighbors*level) + 
                ((rN%neighbors)/level)*neighbors + ((rN/neighbors)%level)*level + (rN%level);
    }

    /** 
     * One possible approach to solve the game board. Good for solving
     * half-filled boards. Bad for filling initially empty boards.  
     * @todo Maybe moving this one to a different class would be a good idea.
     */
    public void solveFastApproach(){
    
        int n = unsolvedCells;
        for(int i=0; i<n; i++){

            Collections.sort(possibleValues);

            int size = possibleValues.get(0).getPossibleValues().size();

            int j = 1;
            while (j<numCells && possibleValues.get(j).getPossibleValues().size() == size)
                j++;

            int choise = (int)(j*Math.random());
            
            ClassicCell c = possibleValues.get(choise);
            
            if (!c.getPossibleValues().isEmpty()) {
                userInsertValue(c.getRowPosition(),
                    c.getPossibleValues().get((int)(c.getPossibleValues().size()
                    *Math.random())));                
                
            }       
        }
    }
    
    /** 
     *  Method which will work with user input, will insert given value in given 
     *  cell, if there is an access granted to insert values to that cell. 
     *  @param rowN Number of cell in row board representation.
     *  @param value Value to be inserted to the cell.
     */
    public boolean userInsertValue(int rowN, int value){
        if (rows.get(rowN).getAccess()){
            return insertValue(rowN, value, true);
        }
        return false;
    }

    /** 
     *  Method inserts value in an empty cell. Excludes value from possible 
     *  values of row, line, square neighbors of this cell. 
     *  Sets given access mode to cell.
     *  @param rowN Number of cell in row board representation.
     *  @param value Value to be inserted to the cell.
     *  @param access Mode of access to be set to the cell. 
     */
    private boolean insertValue(int rowN, int value, boolean access){
        if (rows.get(rowN).getValue()==0 && 
                rows.get(rowN).getPossibleValues().contains(value)){

            rows.get(rowN).setValue(value);
            rows.get(rowN).setAccess(access);
            // Exclude this value from all row neighbors possibleValues.
            int rN = (rowN/neighbors)*neighbors;
            for (int i=0; i<neighbors; i++){
                rows.get(rN+i).excludeFromPossibles(value);
            }
            // Exclude this value from all column neighbors possibleValues.
            int rC = (colN_from_rowN(rowN)/neighbors)*neighbors;
            for (int i=0; i<neighbors; i++){
                columns.get(rC+i).excludeFromPossibles(value);
            }
            // Exclude this value from all square neighbors possibleValues.
            int rS = (sqrN_from_rowN(rowN)/neighbors)*neighbors;
            for (int i=0; i<neighbors; i++){
                squares.get(rS+i).excludeFromPossibles(value);
            }
            unsolvedCells--;
            return true;
        }
        return false;
    }
    
    /** 
     * This method will work for user trying to erase value from given cell.
     * @param rowN rowNumber of cell to erase value from.
     */
    public boolean userEraseValue(int rowN){
        if (rows.get(rowN).getAccess() && rows.get(rowN).getValue()!=0) {
            eraseValue(rowN);
            return true;
        }
        return false;
    }

    /** 
     * Erases value from given cell. Ensures that neighboring empty cells of given cell
     * add value of given cell to their 'possibleValues' if it's not blocked by
     * neighbors of those cells. Also ensures that non-empty neighbors of current
     * cell limit possibleValue of given cell after its erasure.
     * @param rowN Row number of cell to erase. 
     */
    private void eraseValue(int rowN){
        // Save value for later use.
        int value = rows.get(rowN).getValue();
        if (value == 0) return;
        // Erase value
        rows.get(rowN).eraseValue();
        rows.get(rowN).setAccess(true);
        unsolvedCells++;

        // Traverse through row of original cell
        int rowStartNumber = (rowN/neighbors)*neighbors;
        for (int i=0; i<neighbors; i++){

            if (rowStartNumber+i != rowN)
            // If we find non-empty cell in the line exclude its value from original cell possible vales.
            if (rows.get(rowStartNumber+i).getValue()!=0)
                rows.get(rowN).excludeFromPossibles(rows.get(rowStartNumber+i).getValue());
            else { /** For each empty cell found while traversing row, we need
             * to check if 'value' is present in column and square neighbors of
             found cell. If not, add 'value' to 'possibleValues' of found cell.*/
                boolean found = false;
                int j=0;
                int _columnStNum = (colN_from_rowN(rowStartNumber+i)/neighbors)*neighbors;
                int _squareStNum = (sqrN_from_rowN(rowStartNumber+i)/neighbors)*neighbors;
                while (!found && j<neighbors){
                    if (columns.get(_columnStNum+j).getValue()==value) found = true;
                    if (squares.get(_squareStNum+j).getValue()==value) found = true;
                    j++;
                }
                if (!found) rows.get(rowStartNumber+i).addToPossibleValues(value);
            }
        }

        // Traverse through column of original cell
        int columnStartNumber = (colN_from_rowN(rowN)/neighbors)*neighbors;
        for (int i=0; i<neighbors; i++){

            if (columnStartNumber+i != colN_from_rowN(rowN))
            // If we find non-empty cell in the line exclude its value from original cell possible vales.
            if (columns.get(columnStartNumber+i).getValue()!=0)
                columns.get(colN_from_rowN(rowN)).excludeFromPossibles(columns.get(columnStartNumber+i).getValue());
            else { /** For each empty cell found while traversing column, we need
             * to check if 'value' is present in row and square neighbors of
             found cell. If not, add 'value' to 'possibleValues' of found cell.*/
                boolean found = false;
                int j=0;
                int _rowStNum = (columns.get(columnStartNumber+i).getRowPosition()/neighbors)*neighbors;
                int _squareStNum = (columns.get(columnStartNumber+i).getSqrPosition()/neighbors)*neighbors;
                while (!found && j<neighbors){
                    if (rows.get(_rowStNum+j).getValue()==value) found = true;
                    if (squares.get(_squareStNum+j).getValue()==value) found = true;
                    j++;
                }
                if (!found) columns.get(columnStartNumber+i).addToPossibleValues(value);
            }
        }

        // Traverse through square of original cell
        int squareStartNumber = (sqrN_from_rowN(rowN)/neighbors)*neighbors;
        for (int i=0; i<neighbors; i++){

            if (squareStartNumber+i != sqrN_from_rowN(rowN))
            // If we find non-empty cell in the line exclude its value from original cell possible vales.
            if (squares.get(squareStartNumber+i).getValue()!=0)
                squares.get(sqrN_from_rowN(rowN)).excludeFromPossibles(squares.get(squareStartNumber+i).getValue());
            else { /** For each empty cell found while traversing column, we need
             * to check if 'value' is present in row and square neighbors of
             found cell. If not, add 'value' to 'possibleValues' of found cell.*/
                boolean found = false;
                int j=0;
                int _rowStNum = (squares.get(squareStartNumber+i).getRowPosition()/neighbors)*neighbors;
                int _columnStNum = (squares.get(squareStartNumber+i).getColumnPosition()/neighbors)*neighbors;
                while (!found && j<neighbors){
                    if (rows.get(_rowStNum+j).getValue()==value) found = true;
                    if (columns.get(_columnStNum+j).getValue()==value) found = true;
                    j++;
                }
                if (!found) squares.get(squareStartNumber+i).addToPossibleValues(value);
            }
        }
    }

    /** Method used to help in development. Print values of cells on the board.*/
    public void printGrid(){
        int ch=0;
        int ln =0;
        for (int i=0; i<(level*level*level*level); i++){
            int value = rows.get(i).getValue();
            
            if (value != 0) {                
                if (value/10 == 0) System.out.print(" ");
                System.out.print(value + " ");
            } else System.out.print("-- ");
            ch++;
            if (ch % level == 0) System.out.print("| ");
            if (ch==(level*level)) {
                System.out.println();
                ch=0;
                ln++;
            }
            if (ln == level){
                for (int j=1; j<=(level*level); j++) {
                    System.out.print("---");
                    if (j%level==0) System.out.print("+-");
                }
                ln=0;
                System.out.println();
            }
        }
    }
    
    /** This method returns current board level.*/
    public int getLevel(){
        return level;
    }
    
    /** This method returns current number of unsolved cells on the board.*/
    public int getUnsolvedCells(){
        return unsolvedCells;
    }   
    
    /** Returns number of cells on the board.*/
    public int getNumCells(){
        return numCells;
    }

    /** Returns list with all cell values given in row oriented board order.*/
    public ArrayList<Integer> getValues(){
        ArrayList<Integer> list = new ArrayList();

        for (int i=0; i<numCells; i++){
            list.add(rows.get(i).getValue());
        }

        return list;
    }

    /** Returns list with all cell access modes
     * given in row oriented board order.*/
    public ArrayList<Boolean> getAccess(){
        ArrayList<Boolean> list = new ArrayList();

        for (int i=0; i<numCells; i++){
            list.add(rows.get(i).getAccess());
        }

        return list;
    }
    
    /** Returns list with all cell values given in row oriented board order.*/
    public ArrayList<Integer> getPossibleValuesSizes(){
        ArrayList<Integer> list = new ArrayList();

        for (int i=0; i<numCells; i++){
            list.add(rows.get(i).getPossibleValues().size());
        }

        return list;
    }
    
    /** Method needed by Cloneable interface, returns a valid clone of this ClassicGrid. */
    @Override
    public ClassicGrid clone(){
        
        TreeMap<Integer, ClassicCell> copyMap = new TreeMap();
        
        for (int i = 0; i<numCells; i++){
            copyMap.put(i, rows.get(i).clone());
        }
        
        ClassicGrid copy = new ClassicGrid(copyMap);
        
        return copy;
    }
    
    /** Returns TreeMap with copies of all cells given in order they are in rows map.*/
    public TreeMap<Integer, ClassicCell> getCopyGridMap(){
        
       TreeMap<Integer, ClassicCell> copyMap = new TreeMap();
        
        for (int i = 0; i<numCells; i++){
            copyMap.put(i, rows.get(i).clone());
        }
        
        return copyMap;
    }
    
    /** Returns copy of cell with given row number.*/
    public ClassicCell getCopyCell(int rowN){
        
       ClassicCell copy = rows.get(rowN).clone();
        
       return copy;
    }
    
    /** This method will erase values in n random cells.*/
    public void randomCellErase(int n){        
        for (int i=0; i<n; i++){            
            Collections.sort(possibleValues, new AnotherCellCompare());            
            int rand = ((int) (Math.random()*(numCells - unsolvedCells))) + unsolvedCells;               
            eraseValue(possibleValues.get(rand).getRowPosition());            
        }        
    }
    
    /** This method sets user access to all non-empty cells to false.*/
    private void confirmInitialValues(){
        for (int i=0; i<numCells; i++){
            ClassicCell c = rows.get(i);
            if (c.getValue() != 0) c.setAccess(false);
        }
    }
    
    /** 
     * Fill in empty grid with n values, make sure grid have solutions. 
     * @todo so far not working for grid level 5.
     */
    public static ClassicGrid makeSolvableGrid(int lev,int percent){
        
        ClassicGrid grid = new ClassicGrid(lev);
        
        boolean found = false;
        
        int num = grid.getUnsolvedCells()/10;
        
        while (!found){   
            boolean goodRandom = true;
            for (int i=0; i<num; i++){
                Collections.sort(grid.possibleValues, new AnotherCellCompare());
                int cellNumber = (int) (Math.random()*grid.getUnsolvedCells());
                ClassicCell c = grid.possibleValues.get(cellNumber); 
                int index = (int) (c.getPossibleValues().size()*Math.random());
                if (c.getPossibleValues().isEmpty()){ 
                    goodRandom = false;
                    break;
                }
                int inputValue = c.getPossibleValues().get(index);
                grid.userInsertValue(c.getRowPosition(), inputValue);
            }
            if (goodRandom){
                grid.solveFastApproach();
                if (grid.unsolvedCells == 0) found = true; 
            } else grid = new ClassicGrid(lev);
        }  
        grid.randomCellErase(grid.numCells*percent/100);
        grid.confirmInitialValues();
        return grid;
        
    }
    
    /** Inserts n random values in random empty cells, */
    public int insertRandomValues(int n){
        int successful =0;
        for (int i=0; i<n; i++){
            int cellNum = (int) (numCells*Math.random());
            if (!rows.get(cellNum).possibleValues.isEmpty()){
                int index = (int) (rows.get(cellNum).getPossibleValues().size()*Math.random());
                int value = rows.get(cellNum).getPossibleValues().get(index);
                if (insertValue(cellNum, value, true)) successful++;
            }
        }
        
        return successful;
    }
    
    public static class AnotherCellCompare implements Comparator<ClassicCell>{
 
        @Override
        public int compare(ClassicCell c1, ClassicCell c2) {
            if (c1.getValue() == 0){
                
                if (c2.getValue() == 0) return 0; // both cells are empty
                return -1; // second cell not empty and will go to the bottom of the list
            }
            if (c2.getValue() == 0) return 1; // first not empty, will go to bottom
            return 0; // both are not empty
        }
    }   
}
